﻿#include "SizeBalancedTree.h"

SizeBalancedTree::SizeBalancedTree()
{

}

void SizeBalancedTree::macroscopicalBalanced(BinaryTreeNode* head)
{
	if (!head) return;

	auto headParent = head->parent;
	if (!headParent) return;

	if (headParent->left == head && !headParent->right)
	{
		// 右旋
		rightRotate(headParent);
	}
	else if (headParent->right == head && !headParent->left)
	{
		// 左旋
		leftRotate(headParent);
	}
	else
	{
		while (headParent)
		{
			microcosmicBalanced(headParent);
			headParent = headParent->parent;
		}
	}
}

BinaryTreeNode* SizeBalancedTree::add(int value)
{
	auto addedNode = BinarySearchTree::add(value);
	auto addedNodeParent = addedNode->parent;
	macroscopicalBalanced(addedNodeParent);
	return addedNode;
}

void SizeBalancedTree::remove(int value)
{
	auto removedNode = find(value);
	auto removedNodeParent = removedNode->parent;
	BinarySearchTree::remove(value);
	macroscopicalBalanced(removedNodeParent);
}

BinaryTreeNode* SizeBalancedTree::microcosmicBalanced(BinaryTreeNode* head)
{
	if (!head) return nullptr;

	BinaryTreeNode* cur = nullptr;
	if (head->left && head->left->left && head->right && head->left->left->getNodeCount() > head->right->getNodeCount())
	{
		cur = rightRotate(head);
		microcosmicBalanced(cur->right);
		return microcosmicBalanced(cur);
	}
	else if (head->left && head->left->right && head->right && head->left->right->getNodeCount() > head->right->getNodeCount())
	{
		cur = leftRotate(head->left);
		cur = rightRotate(cur->parent);
		microcosmicBalanced(cur->left);
		microcosmicBalanced(cur->right);
		return microcosmicBalanced(cur);
	}
	else if (head->right && head->right->left && head->left && head->right->left->getNodeCount() > head->left->getNodeCount())
	{
		cur = rightRotate(head->right);
		cur = leftRotate(cur->parent);
		microcosmicBalanced(cur->left);
		microcosmicBalanced(cur->right);
		return microcosmicBalanced(cur);
	}
	else if (head->right && head->right->right && head->left && head->right->right->getNodeCount() > head->left->getNodeCount())
	{
		cur = leftRotate(head);
		microcosmicBalanced(cur->left);
		return microcosmicBalanced(cur);
	}

	return head;
}

int main_SizeBalancedTree()
{
	auto tree = new SizeBalancedTree();
	for (int n = 1; n <= 32; n++)
	{
		tree->add(n);
	}

	for (int n=10; n <=20; n++)
	{
		tree->remove(n);
	}

	size_t leftSize = tree->getRoot()->left->getNodeCount();
	size_t rightSize = tree->getRoot()->right->getNodeCount();

	size_t leftDepth = tree->getRoot()->left->getDepth();
	size_t rightDepth = tree->getRoot()->right->getDepth();
	
	delete(tree);
	return 0;
}